#include<bits/stdc++.h>
#define N 100010
#define int long long
#define il inline
#define ct const
#define dl double
#define pk push_back
#define fi first
#define se second
#define sit set<pii>::iterator
#define pii pair<int,int>
using namespace std;
il int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);ch=getchar();
	}
	return x*f;
}
char f__[40];
il void write(int x){
	int cnt=0;
	if(x<0){
		putchar('-');x=-x;
	}
	if(!x) putchar('0');
	while(x){
		f__[cnt++]=x%10+'0';x/=10;
	}
	while(cnt) putchar(f__[--cnt]);
}
int n,K,a[N],pre[N],nxt[N],f[20][N],Q,ans[N];
stack<int> S;
struct ques{
    int x,l,r;
} qus[N];
il void init(){
    while(!S.empty()) S.pop();
    for(int i=1;i<=n;++i){
        while(!S.empty()&&a[S.top()]<=a[i]) S.pop();
        if(!S.empty()) pre[i]=S.top();
        else pre[i]=0;
        S.push(i);nxt[i]=n+1;
    }
    while(!S.empty()) S.pop();
    for(int i=n;i;--i){
        while(!S.empty()&&a[S.top()]<=a[i]) S.pop();
        if(!S.empty()) nxt[i]=S.top();
        S.push(i);
    }
    for(int i=0;i<20;++i) for(int j=0;j<=n+1;++j) f[i][j]=0;
    for(int i=1;i<=n;++i){
        if(a[pre[i]]<a[nxt[i]]) f[0][i]=pre[i];
        else f[0][i]=nxt[i];
        if(pre[i]==0&&nxt[i]==n+1) f[0][i]=0;
    }
    for(int i=1;i<20;++i)
        for(int j=1;j<=n;++j) f[i][j]=f[i-1][f[i-1][j]];
}
il int calc(int x){
    int res=0;
    for(int i=19;i>=0;--i) if(f[i][x]){
        res+=(1<<i);x=f[i][x];
    }
    return res;
}
signed main(){
    freopen("summer.in","r",stdin);
    freopen("summer.out","w",stdout);
    n=read();K=read();a[0]=a[n+1]=2e9;
    for(int i=1;i<=n;++i) a[i]=read();
    int flag=1;Q=read();
    for(int i=1;i<=Q;++i){
        qus[i].x=read();qus[i].l=read();qus[i].r=read();
        if(i>1&&qus[i].x!=qus[i-1].x) flag=0;
    }
    if(n<=1000&&Q<=1000){
        for(int i=1;i<=Q;++i){
            swap(a[qus[i].x],a[qus[i].x+1]);init();
            // for(int j=1;j<=n;++j) cerr<<calc(j)<<" ";
            // cerr<<"\n";
            // return 0;
            for(int j=qus[i].l;j<=qus[i].r;++j) ans[i]+=calc(j)*K+n-1;
        }
    }
    else if(flag){
        init();
        for(int i=2;i<=Q;i+=2)
            for(int j=qus[i].l;j<=qus[i].r;++j) ans[i]+=calc(j)*K+n-1;
        swap(a[qus[1].x],a[qus[1].x+1]);init();
        for(int i=1;i<=Q;i+=2)
            for(int j=qus[i].l;j<=qus[i].r;++j) ans[i]+=calc(j)*K+n-1;
    }
    for(int i=1;i<=Q;++i){
        write(ans[i]);putchar('\n');
    }
	return 0;
}